Міністерство науки і освіти України
Дніпропетровський Національний Університет
Факультет електроніки, телекомунікацій та комп'ютерних систем
Кафедра автоматизованих систем обробки інформації
Розрахункова робота № 1
Графічний метод розв'язання задач лінійного програмування
Виконав: ст. гр. РС-05,
Паляруш А.Б.
Перевірив:
Доцент кафедри АСУ
Саликов В.А
Г. Дніпропетровськ
2007
Постановка завдання
Для виробництва двох видів продукції А і В підприємство використовує 4 групи устаткування (1, 2, 3, 4) на виробництво однієї штуки продукції А потрібно зайняти протягом робочої зміни 1, 0, 5 і 3 одиниць відповідно 1, 2, 3, 4 обладнання, а на виробництво однієї штуки продукції У потрібно 1, 1, 0, 2 одиниць обладнання 1, 2, 3, 4. Є обладнання по групах 1 - 18, 2 - 12, 3 - 24, 4 - 18 одиниць. Підприємство отримує з однієї штуки продукції А 4 гривні чистого доходу і 6 гривень - з однієї штуки продукції В.
Скільки штук продукції кожного виду має виробляти підприємство, щоб отримати найбільший прибуток?
Група устаткування, штук для виробництва одиниці продукції | Прибуток, грн | ||||
1 | 2 | 3 | 4 | ||
А | 1 | 0 | 5 | 3 | 4 |
У | 1 | 1 | 0 | 2 | 6 |
Побудова математичної моделі
Для реалізації графічного методу розв'язання задач лінійного програмування необхідно визначити цільову функцію:
Z = 4 * x1 +6 * x2, де Z → max - цільова функція,
x1 - кількість виготовленої продукції виду А,
x2 - кількість виготовленої продукції виду В.
Далі необхідно визначити обмеження, що задають ОДР:
x 1 + x 2 ≤ 18; випливає з доступної кількості обладнання першої групи
x 2 ≤ 12; випливає з доступного кількості обладнання другої групи
5 * x 1 ≤ 24; випливає з доступного кількості обладнання третин групи
2 * x 1 +2 * x 2 ≤ 18; випливає з доступного кількості обладнання четвертої групи
x1 ≥ 0; умова позитивності;
x2 ≥ 0; умова позитивності;
Побудуємо всі отримані обмеження і цільову функцію:
Тепер можна побачити, що ОДР обмежена (4) x1 + x2 ≤ 9, (3) x1 ≤ 4.8, x1 ≤ 0, x2 ≤ 0.
Найкраще (оптимальне) рішення зазначено червоним хрестиком. Максимальний прибуток досягається в точці (0, 9), А = 0, В = 9; при знаходженні оптимального рішення даного завдання слід пам'ятати, що кількість продукції (так само як і кількість ресурсу) ціле число.
Z (0, 9) = 4 * 0 +9 * 6 = 54 (грн).
Чутливість моделі
Завдяки дослідженню чутливості моделі, ми отримуємо інформацію про цінність ресурсу.
Обладнання групи 1 (блакитний колір на графіку) не є дефіцитним і не впливає на оптимальну точку тому вийшло далеко за ОДР, його дуже багато. Це обладнання стане дефіцитним при зменшенні його кількості на 9 одиниць.
Обладнання групи 2 (зелений колір на графіку) так само не є дефіцитним, однак, при зменшенні його кількості на 3 одиниці воно почне впливати на результат.
Обладнання групи 3 (синій колір на графіку) не дефіцитною. Змінюючи його кількість, при незмінній кількості інших ресурсів, ми не вплинемо на результат тому для виробництва продукції А (саме вона повинна проводитися для максимального прибутку) його витрата дорівнює 0.
Обладнання групи 4 (чорний колір на графіку) є дефіцитним, цінність даного ресурсу можна визначити, збільшивши його кількість на 2 одиниці (тому що саме стільки необхідно для виробництва однієї одиниці продукції А):
Отже, при зміні кількості ресурсу 4 на одиницю прибуток зростає на 3 гривні. Даний ресурс можна збільшувати до 24 одиниць, потім він перестане бути дефіцитним, значить, не буде впливати на оптимальне рішення.